package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/remove-nodes-from-linked-list/
 *
 * 2487. 从链表中移除节点
 * 中等
 * 相关标签
 * premium lock icon
 * 相关企业
 * 提示
 * 给你一个链表的头节点 head 。
 *
 * 移除每个右侧有一个更大数值的节点。
 *
 * 返回修改后链表的头节点 head 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [5,2,13,3,8]
 * 输出：[13,8]
 * 解释：需要移除的节点是 5 ，2 和 3 。
 * - 节点 13 在节点 5 右侧。
 * - 节点 13 在节点 2 右侧。
 * - 节点 8 在节点 3 右侧。
 * 示例 2：
 *
 * 输入：head = [1,1,1,1]
 * 输出：[1,1,1,1]
 * 解释：每个节点的值都是 1 ，所以没有需要移除的节点。
 *
 * @author hanjuntao
 * @date 2025/7/9 0009
 */
public class L_2487_remove_nodes_from_linked_list {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "val:" + val;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(5);
        head.next = new ListNode(2);
        head.next.next = new ListNode(13);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(8);

        ListNode listNode = removeNodes4(head);
        printListNode(listNode);
        // 13,8

        ListNode head2 = new ListNode(5);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(8);


        ListNode listNode2 = removeNodes4(head2);
        printListNode(listNode2);
        // 8

        ListNode head3 = new ListNode(5);
        head3.next = new ListNode(2);
        head3.next.next = new ListNode(2);
        ListNode listNode3 = removeNodes4(head3);
        printListNode(listNode3);
        // 5,2,2
    }

    private static void printListNode(ListNode listNode) {
        ListNode curr = listNode;
        while (curr != null) {
            System.out.print(curr);
            System.out.print(",");
            curr = curr.next;
        }

        System.out.println();
    }

    /**
     * 暴力求解
     *
     * 思路：
     * 1. 判断存在后继节点大于当前节点
     * 2. 如果存在，即删除当前节点
     *
     * 问题：
     * 1. 需要暴力判断当前节点的所有后继节点存在不存在大于当前节点的，这个相当于把需求前置了，导致时间复杂度变高
     * 实际上只需要最终返回单调递减的链表
     *
     * 转变思路：
     * 只考虑当前节点之前的元素，用当前节点决定前面节点的去留，这个明显是用到栈的概念
     *
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     *
     * @param head
     * @return
     */
    public static ListNode removeNodes(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while (curr != null) {
            // 需要判断当前节点的所有后继节点存在不存在大于当前节点的，如果存在则删除当前节点
            boolean exist = ex(curr);
            ListNode next = curr.next;

            if (exist) {
                // 如果当前节点是头节点
                // 更新头节点
                if (head == curr) {
                    head = next;
                } else {
                    prev.next = next;
                }
                // 删除当前节点
                curr.next = null;
                curr = next;
            } else {
                prev = curr;
                curr = next;
            }
        }

        return head;
    }

    private static boolean ex(ListNode curr) {
        int currVal = curr.val;

        curr = curr.next;

        while (curr != null) {
            if (curr.val > currVal) {
                return true;
            }

            curr = curr.next;
        }

        return false;
    }

    /**
     * 单调栈
     *
     * 思路：
     * 由题意可知， 最终返回的结果，一定是单调递减的
     *
     * 链表的数据从头节点开始，依次入栈，如果栈顶的元素小于当前节点，则将栈顶元素弹出，直到栈顶元素大于当前节点，或者栈为空
     * 再将当前节点入栈
     */
    public static ListNode removeNodes3(ListNode head) {
        Stack<ListNode> stack = new Stack<>();

        ListNode curr = head;

        while (curr != null) {
            // 保持单调栈递减
            // 栈不为空，且栈顶元素小于当前节点
            while (!stack.isEmpty() && stack.peek().val < curr.val) {
                stack.pop();
            }

            stack.push(curr);
            curr = curr.next;
        }

        ListNode newHead = null;
        ListNode newCurr = null;

        for (ListNode node : stack) {
            if (newHead == null) {
                newHead = node;
                newCurr = newHead;
            } else {
                newCurr.next = node;
                newCurr = newCurr.next;
            }
        }

        return newHead;
    }

    /**
     * 递归：
     *
     * 算法思想：
     * 1. 递归子问题：
     *   a. 当前节点与子链表的关系
     *     ⅰ. 如果当前节点的值 >= 处理后子链表的头节点的值，说明当前节点仍可以作为头结点，将当前节点的next指针指向处理后的子链表头节点，返回当前节点
     *     ⅱ. 如果当前节点的值 <处理后子链表的头节点的值，说明当前节点不能继续使用了，需要舍弃（当前节点的next指针置为空），返回处理后的子链表头节点
     * 2. 递归边界：
     *   a. 如果当前节点为空或者当前节点的next为空，返回当前节点
     *
     * 思路：
     *
     * 针对当前节点与后续节点，只需要找到后续节点按照逻辑处理过之后的头节点，
     * 比较当前节点与后续节点处理后的头节点，哪个大，则返回哪个节点
     *
     *
     * @param head
     * @return
     */
    public static ListNode removeNodes4(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 递归处理后续节点
        ListNode newHead = removeNodes4(head.next);

        // 如果当前头节点大于后续节点的头节点，则继续使用当前的头节点，并且将当前的头节点的next指向后续节点处理后的头节点
        if (head.val >= newHead.val) {
            head.next = newHead;
            return head;
        } else {
            // 当前头节点小于后续节点处理后的头节点。说明当前头节点不需要了，需要删掉
            // 删除当前节点
            head.next = null;
            // 返回后续节点处理后的头节点
            return newHead;
        }
    }

}
